package tree

import (
	"container/list"
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//根据指定层序遍历list 创建一个二叉树
func CreateBTree(nodes []int) *TreeNode {
	var innerCreate func([]int, int, int) *TreeNode
	innerCreate = func(list []int, index, length int) *TreeNode {
		if index >= length {
			return nil
		}
		//最小值认为是 不存在的节点
		if list[index] == math.MinInt || list[index] == -1 {
			return nil
		}
		root := &TreeNode{Val: list[index]}
		//nextIndex := 2 * index
		//if nextIndex == 0 {
		//	nextIndex++
		//}
		root.Left = innerCreate(list, index*2+1, length)
		root.Right = innerCreate(list, index*2+2, length)
		return root
	}
	return innerCreate(nodes, 0, len(nodes))
}

/**
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftHeight := maxDepth(root.Left) + 1
	rightHeight := maxDepth(root.Right) + 1
	return int(math.Max(float64(leftHeight), float64(rightHeight)))
}

/**
验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。


作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func isValidBST(root *TreeNode) bool {
	return isValidBSTWithRange(root, math.MinInt32, math.MaxInt32)

}
func isValidBSTWithRange(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}
	if !isValidBSTWithRange(root.Left, min, root.Val) {
		return false
	}
	//每个节点如果超过这个范围，直接返回false
	if root.Val >= max || root.Val <= min {
		return false
	}
	if !isValidBSTWithRange(root.Right, root.Val, max) {
		return false
	}
	return true
}
func isValidBSTWithSearch(root *TreeNode, lastVal *int) bool {
	if root == nil {
		return true
	}
	if !isValidBSTWithSearch(root.Left, lastVal) {
		return false
	}
	if root.Val <= *lastVal {
		return false
	}
	*lastVal = root.Val
	if !isValidBSTWithSearch(root.Right, lastVal) {
		return false
	}
	return true

}
func inorderTraversalTree(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var list []int
	list = append(list, inorderTraversalTree(root.Left)...)
	list = append(list, root.Val)
	list = append(list, inorderTraversalTree(root.Right)...)
	return list
}

/**
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true

*/
func isSymmetric(root *TreeNode) bool {
	return isSymmetricHelper(root.Left, root.Right)
}

//非递归实现对称树判断，同样从整体结构考虑，层次遍历比较左右节点是否对称
func isSymmetricWithoutRecursion(root *TreeNode) bool {
	//没有节点，后者只有只有一个叶子结点，一定对称
	if root == nil || (root.Left == nil && root.Right == nil) {
		return true
	}
	queue := list.New()
	queue.PushBack(root.Left)
	queue.PushBack(root.Right)
	for queue.Len() > 0 {
		//层次遍历，然后左子树数据相同侧部分节点对称比较
		//因为要验证对称结构，所以每次出队2个（按照顺序进队列的）
		left := queue.Remove(queue.Front()).(*TreeNode)
		right := queue.Remove(queue.Front()).(*TreeNode)
		//左右节点不对称，或值不一致
		if left == nil || right == nil || left.Val != right.Val {
			return false
		}
		queue.PushBack(left.Left)
		queue.PushBack(right.Right)
		queue.PushBack(left.Right)
		queue.PushBack(right.Left)
	}
	return true
}

//抽象思维  从整体结构角度出发判定，左右子树是否对称，不专注局部的思想
func isSymmetricHelper(left, right *TreeNode) bool {
	//解法：判断二叉树是否是对称，需要从子节点开始比较，两个子节点的值必须相同，
	//并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点
	if left == nil && right == nil {
		//叶子节点，一定是对称的
		return true
	}
	//当前节点，缺失一个左节点或右节点，或者左右节点值不一致，一定不对称
	if left == nil || right == nil || left.Val != right.Val {
		return false
	}

	return isSymmetricHelper(left.Left, right.Right) && isSymmetricHelper(left.Right, right.Left)
}

/**
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
*/
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	queue := list.New()
	queue.PushBack(root)
	//结果数组
	var result [][]int
	for queue.Len() > 0 {
		//层次遍历
		var tmpList []int
		levelSize := queue.Len()
		for i := 0; i < levelSize; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			tmpList = append(tmpList, node.Val)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
		}
		result = append(result, tmpList)
	}
	return result
}

/**
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

解法：递归 每次对半分数组去创建其左右子树

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xninbt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	return sortedArrayToBSTHelper(nums, 0, len(nums)-1)
}

func sortedArrayToBSTHelper(nums []int, start int, end int) *TreeNode {
	if start > end {
		return nil
	}
	mid := (start + end) >> 1
	t := new(TreeNode)
	t.Val = nums[mid]
	//构建左右子树
	t.Left = sortedArrayToBSTHelper(nums, start, mid-1)
	t.Right = sortedArrayToBSTHelper(nums, mid+1, end)
	return t
}
